% Use only LaTeX2e, calling the article.cls class and 12-point type.

\documentclass[12pt]{article}

% Users of the {thebibliography} environment or BibTeX should use the
% scicite.sty package, downloadable from *Science* at
% www.sciencemag.org/about/authors/prep/TeX_help/ .
% This package should properly format in-text
% reference calls and reference-list numbers.
\usepackage[UTF8]{ctex} % 中文
\usepackage{scicite}
\usepackage{bm}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{booktabs, siunitx}
\usepackage{slashed}
\usepackage[hidelinks]{hyperref}
\usepackage[framemethod=tikz]{mdframed} % 用来做插入解释段
\mdfdefinestyle{info}{%
	topline=false, bottomline=false,
	leftline=false, rightline=false,
	nobreak,
	singleextra={%
		\fill[black](P-|O)circle[radius=0.4em];
		\node at(P-|O){\color{white}\scriptsize\bf i};
		\draw[very thick](P-|O)++(0,-0.8em)--(O);%--(O-|P);
	}
}

% Define a custom environment for information
\newenvironment{info}[1][Info:]{ % Set the default title to "Info:"
	\medskip
	\begin{mdframed}[style=info]
		\noindent{\textbf{#1}}
}{
	\end{mdframed}
}

% Use times if you have the font installed; otherwise, comment out the
% following line.

\usepackage{times}

% The preamble here sets up a lot of new/revised commands and
% environments.  It's annoying, but please do *not* try to strip these
% out into a separate .sty file (which could lead to the loss of some
% information when we convert the file to other formats).  Instead, keep
% them in the preamble of your main LaTeX source file.


% The following parameters seem to provide a reasonable page setup.

\topmargin 0.0cm
\oddsidemargin 0.2cm
\textwidth 16cm
\textheight 21cm
\footskip 1.0cm


%The next command sets up an environment for the abstract to your paper.

\newenvironment{sciabstract}{%
\begin{quote} \bf}
{\end{quote}}


% If your reference list includes text notes as well as references,
% include the following line; otherwise, comment it out.

% \renewcommand\refname{References and Notes}

% The following lines set up an environment for the last note in the
% reference list, which commonly includes acknowledgments of funding,
% help, etc.  It's intended for users of BibTeX or the {thebibliography}
% environment.  Users who are hand-coding their references at the end
% using a list environment such as {enumerate} can simply add another
% item at the end, and it will be numbered automatically.

\newcounter{lastnote}
\newenvironment{scilastnote}{%
\setcounter{lastnote}{\value{enumiv}}%
\addtocounter{lastnote}{+1}%
\begin{list}%
{\arabic{lastnote}.}
{\setlength{\leftmargin}{.22in}}
{\setlength{\labelsep}{.5em}}}
{\end{list}}


% Include your paper's title here

\title{离散数学基础}


% Place the author information here.  Please hand-code the contact
% information and notecalls; do *not* use \footnote commands.  Let the
% author contact information appear immediately below the author names
% as shown.  We would also prefer that you don't change the type-size
% settings shown here.

\author
{eleve11}

% Include the date command, but leave its argument blank.

\date{\today}
%%%%%%%%%%%%%%%%% END OF PREAMBLE %%%%%%%%%%%%%%%%

\begin{document}

% Double-space the manuscript.

\baselineskip24pt

% Make the title.

\maketitle

% In setting up this template for *Science* papers, we've used both
% the \section* command and the \paragraph* command for topical
% divisions.  Which you use will of course depend on the type of paper
% you're writing.  Review Articles tend to have displayed headings, for
% which \section* is more appropriate; Research Articles, when they have
% formal topical divisions at all, tend to signal them with bold text
% that runs into the paragraph, for which \paragraph* is the right
% choice.  Either way, use the asterisk (*) modifier, as shown, to
% suppress numbering.

\section{命题逻辑}
    逻辑规则给出了数学语句的准确含义。我们首先得知道逻辑的基本构件\textbf{命题}，
    \textbf{命题}是一个陈述语句，它或真或假。 \\
    例如：
    \begin{enumerate}
        \item $1+1=2$ (真命题)
        \item $2+2=4$ (假命题)
        \item 你多大了? (不是命题)
    \end{enumerate}
    \begin{info}
        如果一个命题p是真命题，它的真值为真，用T表示。如果命题p是假命题，则它的真值为假，用F表示。
    \end{info}
    \subsection{命题的逻辑运算}
    命题的逻辑运算符有合取(对应计算机位运算中AND)、析取(对应计算机位运算的OR)、否命题，真值表如表\ref{tab1}、\ref{tab2}、\ref{tab3}
    \begin{table}
        \centering
        \caption{命题值否定的真值表}
        \label{tab1}
        \begin{tabular}{cc}
            \toprule
            $\bm{p}$ & $\urcorner \bm{p}$ \\
            \midrule
            T & F \\
            F & T \\
            \bottomrule
        \end{tabular}
    \end{table}
    \begin{table}
        \centering
        \caption{两个命题合取的真值表}
        \label{tab2}
        \begin{tabular}{ccc}
            \toprule
            $\bm{p}$ & $\bm{q}$ & $\bm{p} \bigwedge \bm{q}$  \\
            \midrule
            T & T & T \\
            T & F & F \\
            F & T & F \\
            F & F & F \\
            \bottomrule
        \end{tabular}
    \end{table}
    \begin{table}
        \centering
        \caption{两个命题析取的真值表}
        \label{tab3}
        \begin{tabular}{ccc}
            \toprule
            $\bm{p}$ & $\bm{q}$ & $\bm{p} \bigvee \bm{q}$  \\
            \midrule
            T & T & T \\
            T & F & T \\
            F & T & T \\
            F & F & F \\
            \bottomrule
        \end{tabular}
    \end{table}
    \newtheorem{thm}{定义}  % 在局部定义的，可放导言区
    \begin{thm}
        令p和q为命题，p和q的\textbf{异或}(记作$p \bigoplus q$)是这样一个命题，当两个命
        题中恰好有一个命题为真时命题为真，否则为假。
    \end{thm}
    \begin{thm}
        令p和q为命题，\textbf{条件语句}$p \rightarrow q$是命题``如果p，则q''。在条件语
        句$p \longrightarrow q$中，p为假设、前提，p为结论。
    \end{thm}
    两种运算的真值表\ref{tab4}、\ref{tab5} \\
    有条件语句$p \rightarrow q$可以构成一些新的条件语句：
    \begin{enumerate}
        \item \textbf{逆命题}，命题$p \rightarrow q$的逆命题是命题$q \rightarrow p$
        \item \textbf{逆否命题}，命题$p \rightarrow q$的逆否命题是命题$\rightarrow q \rightarrow \urcorner p$(逆否命题是原命题的等价命题)
        \item \textbf{反命题}，命题$p \rightarrow q$的反命题是命题$\urcorner p \rightarrow \urcorner q$
    \end{enumerate}
    举个栗子：命题``每经过一次锻炼或战斗，路飞都会变强''  \\
    逆否命题$\Longrightarrow$如果路飞没变强，那么路飞没有锻炼或战斗 \\
    逆命题$\Longrightarrow$如果路飞变强了，那么路飞经历的锻炼或战斗 \\
    反命题$\Longrightarrow$如果没有经过锻炼或战斗，那么路飞不会变强 \\
    \begin{table}
        \centering
        \caption{两个命题异或的真值表}
        \label{tab4}
        \begin{tabular}{ccc}
            \toprule
            $\bm{p}$ & $\bm{q}$ & $\bm{p} \bigoplus \bm{q}$  \\
            \midrule
            T & T & F \\
            T & F & T \\
            F & T & T \\
            F & F & F \\
            \bottomrule
        \end{tabular}
    \end{table}
    \begin{table}
        \centering
        \caption{条件语句的真值表}
        \label{tab5}
        \begin{tabular}{ccc}
            \toprule
            $\bm{p}$ & $\bm{q}$ & $\bm{p} \longrightarrow \bm{q}$  \\
            \midrule
            T & T & T \\
            T & F & F \\
            F & T & T \\
            F & F & T \\
            \bottomrule
        \end{tabular}
    \end{table}
    \begin{thm}
        令p和q为命题，\textbf{双条件语句}$p \leftrightarrow q$是命题``p当且仅当p''。
        当p和q有相同的真值时，双条件语句为真，否则为假。
    \end{thm}
    双条件语句也代表着q是p的充分必要条件($p \leftrightarrow q \equiv
    (p \leftrightarrow q) \bigwedge (q \leftrightarrow p)$)，其真值表，
    如表\ref{tab6}
    \begin{table}
        \centering
        \caption{双条件语句的真值表}
        \label{tab6}
        \begin{tabular}{ccc}
            \toprule
            $\bm{p}$ & $\bm{q}$ & $\bm{p} \leftrightarrow \bm{q}$  \\
            \midrule
            T & T & T \\
            T & F & F \\
            F & T & F \\
            F & F & T \\
            \bottomrule
        \end{tabular}
    \end{table}

    \subsection{逻辑运算符的优先级}
    同加减乘除一样，逻辑运算发也有优先级，优先级如表\ref{tab7}
    \begin{table}
        \centering
        \caption{逻辑运算符的优先级}
        \label{tab7}
        \begin{tabular}{ccc}
            \toprule
            运算符 & 优先级  \\
            \midrule
            $\urcorner$ & 1 \\
            $\bigwedge$ & 2 \\
            $\bigvee$ & 3 \\
            $\rightarrow$ & 4 \\
            $\leftrightarrow$ & 5 \\
            \bottomrule
        \end{tabular}
    \end{table}

    \subsection{德摩根定律}
    在所有可能的情况下都有相同真值两个复合命题都是逻辑等价的，如表 \ref{tab8} 的两个德摩根定律(Mark: 还未仔细去看，记录在这)
    \begin{table}
        \centering
        \caption{德摩根定律}
        \label{tab8}
        \begin{tabular}{ccc}
            \toprule
            $\urcorner(p \bigwedge q) \equiv \urcorner p \bigvee \urcorner q$ \\
            $\urcorner(p \bigvee q) \equiv \urcorner p \bigwedge \urcorner q$ \\
            \bottomrule
        \end{tabular}
    \end{table}

    \subsection{命题逻辑的应用}
    \begin{enumerate}
        \item 语句翻译
        \item 系统规范说明
        \item 布尔搜索，大量用于web搜索技术
        \item 逻辑谜题
        \item 逻辑电路
    \end{enumerate}

    \subsection{谓词与量词}
    来看一个栗子：$x>3$这个语句是否正确呢？在未给定$x$条件下，答案是无法确定的。那么我们如何
    将这样一个无法确定的句子生成为命题呢？\\
    令$P(x)$表示语句$x>3$ (函数化语句)，由此$P(4) \Longrightarrow 4>3$则为真
    ，同样操作，$P(2)$则为假。
    \begin{thm}
        一般地，涉及到$n$个变量$x_1, x_2, \ldots, x_n$的语句可以表示成
        $P(x_1, x_2, \ldots, x_n)$形式，语句$P(x_1, x_2, \ldots, x_n)$是
        \textbf{命题函数}$P$在$n$元组$(x_1, x_2, \ldots, x_n)$的值，$P$被称为$n$元
        \textbf{谓词}
    \end{thm}
    当然另外一种方式可以从命题函数生成一个命题，就是\textbf{量化}，量化限制了命题在哪个范围
    内是成立的，``所有，某些，许多，没有''，当然离散数学利用到的连词如表\ref{tab9}
    \begin{table}
        \centering
        \caption{量词}
        \label{tab9}
        \begin{tabular}{ccc}
            \toprule
            命题 & 什么时候为真 & 什么时候为假 \\
            \midrule
            $\forall _xP(x)$(全称量词) & 对于每一个$x$，$P(x)$都为真 & 有一个$x$，使$P(x)$都假 \\
            $\exists _xP(x)$(存在量词) & 有一个$x$，使$P(x)$为真 & 对于每一个$x$，$P(x)$都为假\\
            \bottomrule
        \end{tabular}
    \end{table}
    \subsubsection{量词的德摩根定律}
    量词的否定的规则称为量词的德摩根定律，规则总结见表\ref{tab10}
    \begin{table}
        \centering
        \caption{量词的德摩根定律}
        \label{tab10}
        \begin{tabular}{cccc}
            \toprule
            否定 & 等价语句 & 何时为真 & 何时为假 \\
            \midrule
            $\urcorner \exists _xP(x)$ & $\forall _x \urcorner P(x)$ & 对每个$x$，$P(x)$为假 & 有$x$，使得$P(x)$为真 \\
            $\urcorner \forall _xP(x)$ & $\exists _x \urcorner P(x)$ & 有$x$，使得$P(x)$为假 & 对于每个$x$，$P(x)$为真 \\
            \bottomrule
        \end{tabular}
    \end{table}

\section{离散数学中的基本结构}
    \subsection{集合}
    集合，最基本的离散结构，其中的元素是无序聚集在一起的。所有其他离散结构都建立在集合之上。
    常见的集合有$\bm{N}$(自然数集)，$\bm{Z}$(整数集)，$\bm{Q}$(有理数集)，$\bm{R}$(
    实数集).
    \subsubsection{文氏图}
    集合可以使用文氏图形象的表示。就像下图 \\
    \includegraphics[scale=0.75]{venn.png}
    \subsubsection{子集、集合的大小、幂集}
    \begin{thm}
        集合$A$是集合$B$的子集，当且仅当集合$A$的每个元素都属于集合$B$，用符号$A
        \subseteq B$表示集合$A$是集合$B$的子集。
    \end{thm}
    \indent \textbf{集合的大小}，例如上图的$A$集合的大小：$|A|=10$，$10$是集合$A$的
    \textbf{基数} \\
    \indent 许多问题都涉及到要检查一个集合$A$的所有可能的组合是否满足某一种性质，为了这一目
    的，需要构造一个集合包含集合$A$的所有子集作为新集合。这个新集合就是集合$A$的幂集。\\
    \indent 举个栗子，集合$\{ 0, 1, 2 \}$的\textbf{幂集}：\\
    \begin{displaymath}
        \{ \emptyset, \{ 0 \}, \{ 1 \}, \{ 0, 1 \}, \{ 0, 2 \}, \{ 1, 2 \}, \{ 0, 1, 2 \} \}
    \end{displaymath}
    \subsubsection{笛卡尔积}
    有时候元素聚集的次序是重要的，这时就需要有序n元组来表示了。
    \begin{thm}
        有序n元组$(a_1, a_2, \ldots, a_n)$是以$a_1$为第一项，以$a_2$为第二项，以$a_n$
        为第n项的有序聚集。
    \end{thm}
    \begin{thm}
        集合$A_1, A_2, \ldots, A_n$的笛卡尔积是用$A_1 \times A_2 \times \ldots
        \times A_n$表示，是有序n元组$(a_1, a_2, \ldots, a_n)$的集合，其中$a_i$属于
        $A_i$，$i=1, 2, \ldots, n$，换言之，$A_1 \times A_2 \times \ldots
        \times A_n = \{ (a_1, a_2, \ldots, a_n) | a_i \in A_i, i=1,2,\ldots,n \}$
    \end{thm}
    举两个栗子
    \begin{eqnarray*}
        \textrm{e.g.1} \quad
				A=\{ 1, 2 \}, B= \{ a, b, c \}, \quad A \times B = ? \\
        A \times B = \{ (1, a), (1, b), (1, c), (2, a), (2, b), (2, c) \} \\
        \textrm{e.g.2} \quad
				A=\{ 1, 2 \}, B= \{ a, b \}, C = \{ 0, 1, 2 \} \quad A \times B \times C = ? \\
        A \times B \times C = \{ (1, a, 0), (1, a, 1), (1, a, 2), (1, b, 0),
        (1, b, 1), (1, b, 2), \\ (2, a, 0), (2, a, 1), (2, a, 2), (2, b, 0), (2, b, 1), (2, b, 2) \}
    \end{eqnarray*}

\section{关系}
		我们可以使用两个相关元素构成的有序对来表达两个集合元素之间的关系，这是一种最直接的方式。
		为此，由有序对组成的集合就叫二元关系(表示两个集合元素之间的关系)。
		\begin{thm}
        设A和B是集合，一个从A到B的二元关系是$A \times B$的子集。用aRb表示
				$(a,b) \in R$，$a\slashed{R}b$表示$(a,b) \notin R$，当$(a,b)$属于R时，
				称a与b有关系R。
    \end{thm}
		集合关系的性质有(下面栗子中集合$A=\{ 1,2,3,4 \}$):
		\begin{enumerate}
				\item 自反关系：若对每个元素$a \in A$有$(a, a) \in R$，那么定义在集合A上的关系
				R称为自反的。$R=\{ (1,1),(1,2),(2,2),(3,3),(4,2),(4,4) \}$
				\item 对称关系：对于任意$a,b \in A$，若只要$(a,b) \in R$就有$(b,a)\in R$,则
				称定义在集合A上的关系R是对称的。$R=\{ (1,1),(1,2),(2,1) \}$
				\item 反对称关系：对于任意$a,b \in A$，若只要$(a,b) \in R$且$(b,a)\in R$，
				一定有$a=b$，则称定义在集合A上的关系R是反对称的。也即当存在关系$(a,b) \in R$且
				$a \neq b$，不存在$(b,a) \in R$。
				$R=\{ (2,1),(3,1),(3,2),(4,1),(4,2),(4,3) \}$
				\item 传递关系：对于任意$a,b,c \in A$，$(a,b) \in R$并且$(b,c) \in R$，则
				$(a,c) \in R$，称定义在集合A上的关系R是传递的。
				$R=\{ (2,1),(3,1),(3,2),(4,1),(4,2),(4,3) \}$
				\item 等价关系：如果关系是自反、对称、传递的。
		\end{enumerate}
		\subsection{闭包}
		一般来说，设关系R为集合A上的关系，关系R可能具备或者不具备某些性质P，例如自反关系、传递关
		系，如果存在包含R的具备性质P的关系S，并且S是所有包含R且具有性质P的关系的子集，那么S叫做
		R的关于性质P的\textbf{闭包}。

\newpage
\begin{thebibliography}{99}
    \bibitem{ba} Kenneth H.Rosen著, 徐六通等译. 离散数学及其应用 (2015).
\end{thebibliography}

\end{document}
